AtCoder Library
練習用コンテストで一通りACした解説
とりあえず確認してみたら1/3から1/2くらい既に実装してあった。今はリポジトリにバラバラに散らばってるので後でACLと同じディレクトリ構造にしてMITライセンスにしとこう。
残りの未実装なものは公式が「これは頻出アルゴリズムだ」と言ってるわけだからなるはやで実装する。
AtCoder Library の Python 実装，普通にいろんなアルゴリズムを実装するとかはすでにいっぱいある（≒ yosupo judge や AOJ から取ってこればよい）はずだから，numpy/scipy/networkx とか cython とかでゴリゴリに高速化したものができてほしい src Practice ContestのAll Submitの所要時間順ランキングがライブラリ速度を競い合う場になるのではないかと思ってる
僕は以前NumbaやCythonでの高速化にハマってたのだけど、最近は一周回ってPyPyで柔軟性を犠牲にせずに速くすることに興味がある 内容
部分和の計算と要素の更新の両方を効率的に行える木構造(Binary Indexed Treeとも呼ばれる)
固定個数の要素がランダムアクセスで更新される時に総和や最小値をO(logN)で求めることができる木
文字列アルゴリズム詰め合わせ
z_algorithm
数学アルゴリズム詰め合わせ
pow_mod
inv_mod
crt
Modint 自動でmodを取る構造体
Pythonだと演算子のオーバーロードで実現したら見た目は綺麗だけど、これを使うシチュエーションは関数呼び出しのオーバーヘッドを払えない状況だと思う
グラフ
無向グラフに対して、辺の追加、頂点が連結かの判定、をならし O(α(n)) 時間で処理
有向グラフを強連結成分分解
$ \bigvee (x_{i0} = v_{i0} \wedge x_{i1} = v_{i1}) の形の論理式を充足する割当が存在するかを判定し、する場合にはその割当の一つを得る
ここで練習できる
Python関連記事